This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

2
votes
1answer
42 views

Interesting Nim Variant - a new stone game

this is from http://poj.org/problem?id=1740 Alice and Bob decide to play a new stone game.At the beginning of the game they pick n(1<=n<=10) piles of stones in a line. Alice and Bob move the ...
1
vote
1answer
34 views

How to use nCr(n,k) with unordered sampling with replacement?

You go to a bakery to select some baked goods for a dinner party. You need to choose a total of 12 items. The baker has 7 different types of items from which to choose, with lots of each type ...
2
votes
1answer
34 views

Evaluation of a limit of ratio of sums [closed]

How do I calculate the value of $$ \lim_{n\to \infty} \left(\frac{\sum_{r=0}^{n} \binom{2n}{2r}3^r}{\sum_{r=0}^{n-1} \binom{2n}{2r+1}3^r}\right)$$
0
votes
2answers
42 views

Adding Combinations - Math Contest

I am studying for a math test, and I'm wondering on an easier way to add combination series. For example, $12 \choose 3$ + $12 \choose 4$ + ... + $12 \choose 8$. Is there an easier way than: $2^{12}$ ...
0
votes
1answer
34 views

Calculating invariant for T shape tetrominos on rectangular board

The question is from Roland Backhouse Algorithmic Problem Solving. Suppose a rectangular board can be covered with T-tetrominoes. Show that the number of squares is a multiple of 8. The ...
0
votes
0answers
23 views

A question regarding a combinatorial design.

I've been given the following question, and it almost seems too simple, so I'm not really too sure whether I'm just trying to overthink things. Let $B_0$ be a block of a $(v,k,1)$-design $(X, ...
2
votes
3answers
109 views

Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2} $ I'm trying to prove this by counting but ...
0
votes
0answers
33 views

Special partition of a number $n$

Given any integer $n$, how many ways can it be partitioned in which the number $1$ is not allowed? For instance, if $n=6$, then the partitions obeying the aforementioned rule are $6+0$, $4+2$, $3+3$, ...
0
votes
2answers
64 views

Number of Integer Solutions Problem

An elevator in the Empire State Building starts at the basement with 57 people (not including the elevator operator) and discharges them all by the time it reaches the 86th floor. In how many ways ...
1
vote
1answer
74 views

Proof of an identity involving binomial coefficients

I have found numerically that the following identity holds: \begin{equation} \sum_{n=0}^{\frac{t-x}{2}} n 2^{t-2n-x}\frac{\binom{t}{n+x}\binom{t-n-x}{t-2n-x}}{\binom{2t}{t+x}} = ...
5
votes
0answers
43 views

How can a finite graph be viewed as a discrete analogue of a Riemann surface?

In the paper "Riemann–Roch and Abel–Jacobi theory on a finite graph" by Baker and Norine, the first line of the abstract states: "It is well known that a finite graph can be viewed, in many respects, ...
4
votes
4answers
213 views

Alternating sum of binomial coefficients multiplied by (1/k+1)

I'm trying to prove that $$\sum_{k=0}^n {n \choose k} (-1)^k \frac{1}{k+1} = \frac{1}{n+1}$$ So far I've tried induction (which doesn't really work at all), using well known facts such as ...
-4
votes
1answer
185 views

Count good numbers in between L and R

Let length(A) denote the count of digits of a number A in its decimal representation. All non-negative numbers of length 1 are Good. Further, a number X with length(X) $≥ 1$ can also be considered ...
1
vote
4answers
57 views

How to calculate $\sum\limits_{k=0}^{n}{k\dbinom{n}{k}}$ [duplicate]

I derived this sum from a problem I have been working on. Somehow I don't know how to proceed. I only know some basics like $\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n$. Meanwhile I am reading the ...
1
vote
0answers
20 views

A Burnside's Lemma related problem

Alex is a necklace maker. He likes this task because it's challenging, fascinating and of course makes a lot of money. Now, he wants to make a necklace consisting of n beads. The beads are connected ...
2
votes
0answers
94 views

Beads on the circle [duplicate]

It is placed the $n$ beads on a circle, $n \geq 3$. They numbered in random order. They are viewed clockwise. Beads for which the number of the previous bead less than the number of a next bead, are ...
2
votes
1answer
39 views

Counting the ways to color $k$ marbles blue in the circle with $m$ red marbles such that no neighbouring blue marbles

Let $m$ be a positive integer. The numbers $1,2, \cdots , m$ are evenly spaced around a circle. A red marble is placed next to each number. The marbles are indistinguishable. Adrian wants to choose ...
1
vote
1answer
19 views

Number of paths in a rectangle from top left corner to bottom right corner

Given a rectangle of heigh $H$ and width $W$, a smaller rectangle of height $A$ and width $B$ is cut out from the top-right corner of the rectangle. $H,W,A,B \subset I$. $I$ denotes the set of ...
1
vote
1answer
29 views

Product of binomial coefficients

Is there any way to simplify given expression ($j$ and $i$ are given, $n\leq \lfloor j/i \rfloor$) $$\prod_{x=1}^n \binom {j-(x-1)i} {i}$$ (e.g. in terms of factorials)? Thanks!
6
votes
5answers
129 views

Verify the following combinatorial identity: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$

$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$ Nice, so I've proven some combinatorial identities before via induction, other more simple ones by committee selection models.... But ...
0
votes
1answer
23 views

prove that a partially ordered set of elements mn+1 has a chain of size m+1 or antichain of size n+1

Theorem Required. Not sure how to solve this problem,my idea is to suppose that such antichain exist and construct a chain, and suppose that a chain exist a prove and create such antichain. not ...
0
votes
0answers
13 views

Chains and antichains on partial order(divisibility)

Hi guys, I have this problem, but i dont quite understand it,I know that the size of the largest chain is 4, because 1|2|4|8 and 1|3|6|12. On the other hand, i know that one antichain of the largest ...
1
vote
0answers
28 views

Any good books on math puzzles and nim games?

Are there any good books on nim games, math puzzles, and games where players take turns, player A moves somehow, player B moves somehow, etc? I tried using Engel's book by it is a bit too advanced for ...
0
votes
0answers
19 views

The size of largest antichain to the total number of incomparable elements

Given a poset $>$ over a set $A$, every two elements $x,y\in A$ stands in exactly one of three cases: either $x>y$ or $y>x$ or $x\bowtie y$. The last case says $x$ and $y$ are incomparable. ...
1
vote
2answers
35 views

Get the probability out of a combination of events

I'm learning probability. I'm having troubles with combinations. I think I'm not taking the right events of combinations. Please read the problem and tell me if what I did is correct. If not I ...
0
votes
2answers
52 views

Sum of the product of two combinations

Could anyone explain how this statement is true? You may notice that this statement is part of the process of adding two independent binomial r.v.'s. $$ \ \sum_{x=0}^\infty{n \choose x}{m \choose ...
4
votes
3answers
108 views

A question in permutation

Help is needed in solving the following problem. $8$ persons ($A$ and $B$ and $P, Q, R, S, T, U$) are to be seated in $2$ rows ($4$ seats per row). Find the number of ways that $A$ and $B$ are ...
4
votes
0answers
85 views

Can -9 to 9 be placed in 41 lines of zero?

The cubic curve $2x^3-4x^2y+2xy^2-8x+y^3-y$ can be used to get lattice points allowing the placement of the numbers $-8$ to $8$ so that all 32 triplets that sum to 0 will be a straight line of three. ...
1
vote
1answer
37 views

Equation for a systematic permutation

A $6$ digit number is set whereby every digit can be repeated without any constraints. So one can have a number between $000001$ and $999999$. (Zeros on the left are counted). The problem: Generate ...
0
votes
0answers
51 views

Permutation and combination identity

Prove that $\displaystyle \sum_{i=0}^n \binom{n}{i}\binom{m+i}{n}=\sum_{i=0}^n \binom{n}{i}\binom{m}{i} 2^i$ for natural numbers $m,n.$ The question doesn't seem to have any direct combinatorial ...
1
vote
1answer
29 views

How many 10 bit words contain at least three '1' and three '0'?

I need some help with combinatorics. I have to count all the 10 bit words that contain at least 3 '1' and 3 '0', so I guess that the words would be something like this: $$111 000 xxx x$$ The problem ...
1
vote
0answers
30 views

no. of regions a plane is divided into by $n$ lines in general position

My notes state the Counting process for knowing no. of regions a plane is divided into by $n$ lines in general position := Let $h_1(n)=$ No. of parts a line is divided by $n$ distinct ...
12
votes
4answers
242 views

An ant on an infinite chessboard

There is an infinite chessboard, and an ant $A$ is in the middle of one of the squares. The ant can move in any of the eight directions, from the center of one square to another. If it ...
0
votes
1answer
32 views

Proof using pidgeon-hole principle [duplicate]

If we have the set $Y=\{1,2,3...2014\}$ and $X$ is some subset of $Y$, I'm to prove that if $|X|\geq64$ then there exists pairs $\{x,y\}$ and $\{a,b\}$ for some $x,y,a,b \in X$ for which $|x-y| = ...
1
vote
0answers
44 views

Number of vectors which are $\alpha$ angle apart

Let, $A\subseteq\{z=(z_1,z_2)\in\mathbb{C}^2:|z|^2=|z_1|^2+|z_2|^2=1\}$ such that any two vectors in $A$ have angle between them $\ge\alpha$ for some $0<\alpha<1$. I want to prove that ...
-1
votes
0answers
35 views

How do you make the lighest change possible?

Suppose you have coin denominations $1 = c_1 < c_2 <... < c_k$ each with associated weight $w_1, ..., w_k$ and that you are trying to make change for $n$ cents. How can you make the ...
1
vote
2answers
40 views

The probability that no cup is upon a saucer of the same color

Six cups and saucers come in pairs: there are two cups and saucers that are red, white, and blue. If the cups are placed randomly onto the saucers (one each), find the probability that no cup is upon ...
1
vote
1answer
30 views

Five digit numbers where each digit can appear up to three times

The question is to determine how many five-digit numbers there are (using the digits 0-9) where each digit can appear up to three times in the number. The total number of numbers that can be made ...
2
votes
0answers
42 views

Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$. This is a fact that I have read in several ...
0
votes
1answer
35 views

$3\times 3$ seats need to be taken this way.

Suppose we have 9 seats named like this: Seats $b_i$ can be taken if $a_i$’s are already taken. And $c_i$’s can be taken if $b_i$’s are taken. The question is in how many ways can 9 individuals ...
2
votes
3answers
79 views

Distribution of number of unique elements

I've been stuck on the following problem for a few days and would really appreciate some help. This isn't homework. The context of this problem is that $m$ and $n$ may be extremely large but there's ...
0
votes
0answers
14 views

Combinatorical probability - Hamburger placement

The question goes: " Three friends order a hamburger for themselves. All order a different hamburger. The waitor puts up the three hamburgers on the table completely randomly. What is the probability ...
0
votes
0answers
53 views

arranging people into seats in a row

Suppose there are 100 people in a line and they are to be arranged into 100 chairs in a row. Each of them has already selected one number $x_i$ from $1$ to $100$ randomly (i.e. all numbers with equal ...
0
votes
2answers
27 views

How to calculate a group probability

Problem: If I have 10 monkeys and 30 bananas, and the monkeys are all equally likely to eat each banana. What is the probability that every monkey eats at least 2 bananas? Could someone ...
17
votes
4answers
2k views

Incredible Blackjack Hand

Last Saturday night I played at Bally's in Atlantic City and got a hand I could not believe. Dealer had 9 and I was dealt 2 8s. I split the 8s and was given a third card. It was an 8 so I split them ...
1
vote
2answers
45 views

no. of ways of $\displaystyle S = \{1,2,3,4,5,6,…,12\}$ is partitioned into three sets $A,B,C$ of equal size

Let $\displaystyle S = \{1,2,3,4,5,6,.....,12\}$ is partitioned into three sets $A,B,C$ of equal size such that $A\cup B\cup C = S$ and $A\cap B\cap C = \phi.$ Then no. of ways to partition $S$ is ...
0
votes
1answer
23 views

Tom can choose from $4$ soups, $5$ salads and $4$ drinks for his lunch. How many different combinations of a soup, a salad, and a drink can he make? [closed]

Tom can choose from $4$ soups, $5$ salads and $4$ drinks for his lunch. How many different combinations of a soup, a salad, and a drink can he make? Any help is appreciated. Combinations or ...
1
vote
1answer
31 views

Reduced Row Echelon Form in $\Bbb Z/3\Bbb Z$?

I'm trying to understand the best way to approach this problem. Short of writing every combination of matrices, I'm wondering if anyone can help me learn how to solve this problem. How many $3\times ...
0
votes
2answers
32 views

Division 16 persons into 4 groups

How many ways to divide 16 persons to 4 groups ? (there is no empty group) ? I have two ideas, but I don't know what is ok: Strirling number: $\{^{16}_{\ 4}\}$ or ${16\choose 4} \cdot 4^{12}$
1
vote
1answer
34 views

Combinatorial or algebraic proof

I am having trouble proving this identity using combinatoric or algebraic proof. As someone pointed me out it is somehow related to pascals triangle recurrence. $$\sum_{i=0}^k \binom{n+i}{i} = ...