For 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 (4)

2
votes
1answer
614 views

What is the probability of having a cycle of length three in an Erdős-Rényi graph?

Given an Erdős-Rényi graph $G(n,p)$ (that is, a random graph where each edge exists with probability $p$), what is the probability of having a "triangle"? Given $3$ nodes in the graph, the ...
4
votes
1answer
79 views

Number of realizations of particular triad type

Given four types of triads (figure below) their probabilities in a random Bernoulli digraph are as follows: $T_{003}$: $(1-p)^6$ $T_{012}$: $6p(1-p)^5$ $T_{102}$: $3p^2(1-p)^4$ $T_{111D}$: ...
4
votes
4answers
2k views

Proving q-binomial identities

I was wondering if anyone could show me how to prove q-binomial identities? I do not have a single example in my notes, and I can't seem to find any online. For example, consider: ${a + 1 + b \brack ...
1
vote
2answers
2k views

How many ways to place $n$ balls in $k$ bins with the minimum number of balls in any bin equal to $m$?

I apologize if this question does not make sense. I have $k$ bins and $n$ balls. $m$ represents the size of the smallest bin in terms of how many balls it contains. For example if I have five bins ...
2
votes
0answers
90 views

Number of planar triangulations

So I am given $n$ points in the plane and I want to create a planar graph such that every face is bounded by $3$ edges (even the "outside" face). Hence if I have say $4$ vertices, then there is a ...
1
vote
1answer
177 views

Permutation of NBA playoffs

I have a the link below to show the Bracket I was given(the teams are different, that should not make a difference) There is 16 teams on the Sheet i was given, with what it looks like if the brackets ...
4
votes
1answer
599 views

Generating Functions: Partitions of Integers

I'm somewhat stuck on a problem involving using generating functions to determine the number of possible solutions to an equation. I've attempted to solve the problem by following an example in my ...
0
votes
1answer
264 views

Principle of Inclusion / Exclusion Word Problem

I'm just trying to understand how to use PIE one word problems. I've got this silly situation in front of me: A woman is having a dinner party with 9 of her female friends, and she's every so nicely ...
2
votes
1answer
64 views

Permutation of Dresses [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? How many number of ways I can wear four dresses for n days without wearing the same dress for two ...
1
vote
1answer
77 views

Arranging Objects on a 4x4 Board

In how many ways can one put 2 distinguishable objects on a 4x4 board? In how many ways can one put them so that when you rotate the board to 90 degrees the positions of objects is preserved?
0
votes
1answer
537 views

In how many ways can you make a necklace with $n$ black beads and $m$ white beads? [duplicate]

Possible Duplicate: Number of different necklaces using $m$ red and $n$ white pebbles I don't understand high level maths. Please try to do simple$\ldots$ I tried to hunt down the pattern ...
3
votes
1answer
356 views

Combinatorics: How many solns to equation? (principle of inclusion / exclusion)

So I'm having a lot of trouble understanding the logic in my Combinatorics class. I've got this question for an assignment: How many solutions are there to $x_1 + x_2 + x_3 + x_4 = 19$, $x_i \geq 0$ ...
7
votes
2answers
205 views

Self-avoiding walks

Let $c_n$ be the number of self-avoiding walks in ${\mathbb Z}^2$ of length $n$. Because $c_n$ is a submultiplcative sequence ($c_{n+m} \leq c_nc_m$ for all $n, m \geq 1$), Fekete's lemma tells us ...
0
votes
1answer
67 views

Formalize as combinatorics problem (get all sets that boolean sum == (1,1,1))

I have such a problem: there are several boolean tupels (properties of some objects) K1 = (0, 1, 0) K2 = (1, 1, 0) K3 = (1, 1, 0) K4 = (0, 0, 1) K5 = (0, 0, 1) I ...
1
vote
1answer
207 views

BIBD- block design question combinatorics

Prove that a balanced, uniform incomplete design is regular. For this question, I have no clue where to start, any suggestions?
1
vote
1answer
88 views

Counting Graphs

This problem actually relates to multi processing computer architecture, but boils down to a mathematical expression quite difficult to understand. The image below explains the problem and the last ...
4
votes
2answers
512 views

Limit of alternating sum with binomial coefficient

I need to find a limit, or approximation for $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(a+bk)$ for, say, an $a,b\in (0,10)$. It is not so important what values $a$ and $b$ have. It would be ...
3
votes
1answer
181 views

Counting in how many ways rocks can be put in boxes

How can I figure out the following questions? How many possible combinations can be done by having 26 boxes and 15 red rocks, and 15 black rocks? Each box can have up to 15 rocks in it. We can have ...
3
votes
1answer
2k views

Scheduling 12 teams competing at 6 different events

I have a seemingly simple question. There are 12 teams competing in 6 different events. Each event is seeing two teams compete. Is there a way to arrange the schedule so that no two teams meet ...
1
vote
0answers
147 views

How should I interpret Johnson's “Note on the '15' puzzle”?

Following the suggestion of Gerry Myerson who commented below, I went ahead and read Johnson's "Note on the '15' Puzzle". Bearing in mind that I am not well versed in the English of 19th century ...
1
vote
1answer
159 views

Combinatorics problem based on Ferrers graph

Need help with this proof using Ferrers' graph or otherwise. Show that the number of partitions of $r+k$ into $k$ parts is equal to The number of partitions of $r + {k+1 \choose 2}$ into $ k $ ...
6
votes
1answer
84 views

Combinatorics: likelihood of a uniform draw

An urn contains 10 kinds of pebbles, and 100 pebbles of each kind. We draw 100 pebbles (without replacement). What is the probability that we get between 8 and 12 pebbles of each kind?
18
votes
1answer
307 views

Count the number of bases in a subset

Consider $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the subset $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. How many ...
4
votes
1answer
102 views

Proof about binomial coefficient

I today see a approximated equation, when $n \ll u $: $$\log {u \choose n} \approx n \Big(\log \frac{u}{n} + 1.44\Big)$$ I would like to know how to prove it.
0
votes
3answers
56 views

Subgroups of $\Bbb Z_n$

Consider the cyclic group $\Bbb Z_n=\{1,2,\cdots n\}$ under addition modulo $n$ and for some non zero $a\in \{1,2,\cdots n-1\}$ let $\langle a\rangle=H\le \Bbb Z_n$ of order $q$. I wish to show that ...
1
vote
0answers
35 views

What is the link of the origin of a polyhedral fan?

I am trying to understand the article http://arxiv.org/abs/0804.3651 by David Helm and Eric Katz. There the link of the origin of a polyhedral fan is mentioned. I googled and only found definitions ...
2
votes
2answers
245 views

Coloring points on an n-gon

Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color? (Inspired by 2011 AMC 12 A #16 – I'm able to do this for ...
1
vote
1answer
255 views

Prove the symmetric balanced incomplete block design doesn't exist

If $v$ is odd, $k = 5\mod 8$, and $\lambda = 3\mod 4$ then there is no $(v, k, \lambda)$- symmetric balanced incomplete block design. ($\lambda$ is the index) I know that $v$ is odd so I can show ...
1
vote
1answer
2k views

If a die is rolled thrice, what are the possible different outcomes.

I have a single die, and it is rolled thrice. What could be the total possible different outcomes, I guess if I have the number of possible outcomes for each rolled die, then I would use it for other ...
1
vote
1answer
167 views

Permutation by interchange.

I made a conjecture today Start from $1, \ldots, n$, by interchanging the position of $i$ and $j$ where $i < j$ in each step, we are able to get any permutation of $\{1, \ldots, n\}$. Do you ...
28
votes
1answer
1k views

Expiring coupon collector's problem

The well-studied coupon collector's problem asks, given $N$ different coupons from which coupons are being drawn with equal probability and with replacement: How many coupons do you expect to need ...
2
votes
3answers
487 views

Onto maps between two finite sets

Suppose we have $$A = \{a_1,a_2,\ldots,a_5\}, B = \{b_1,b_2,\dots,b_4\}$$ Problem: Count the number $k$ of onto functions $g_j$ (over the integers thru $k$) such that $g_j(a_1) \neq g_j(a_2)$ for all ...
4
votes
4answers
141 views

Binomial series with two binomial coefficents

My question reads: Does this formula has mathematical meaning at first place? Is it summable? $$\sum^{\infty}_{k=0}{n\choose k}{m\choose k} x^k$$
1
vote
1answer
235 views

Latin Squares - Proving the Unique number of Sudoku that can be generated

I recently read that the Sudokus are just Latin Squares for $n = 9$. I know that proving the number of Latin Squares is considered difficult to generalize in terms of $n$. I would like to know if ...
0
votes
1answer
30 views

A fomula for the number of possibilities to express $k$ in $n$ summands

Let $\mathcal{M}(n,k) := \{ \, m\in\mathbb{N}^n \,\,\lvert \,\,\, \sum_{i=1}^n m_i = k \,\}$, where $\mathbb{N}$ denotes the natural numbers with the $0$. Also, let $M(n,k) := |\mathcal{M}(n,k)|$ ...
0
votes
2answers
444 views

Combinatorial proof for choosing k non adjacent balls from n balls is (n-k+1) choose k [duplicate]

Possible Duplicate: Combinatorial proof Arranging people in a row This is a home work problem that I am not able to proceed. Please advice.
2
votes
1answer
140 views

Probability of finding a fit for bin packing

Given that I know the total available space for a set of bins, and the number of bins, I'm trying to determine how likely it is that an item of size $n$ will fit into one of the bins. As an example, ...
1
vote
4answers
2k views

How many ways balls can be selected?

I am trying to solve In how many ways can 25 balls be selected from a bag containing 15 identical red balls, 20 identical blue balls and 25 identical green balls? Should not be the answer be - $$ ...
2
votes
0answers
300 views

sum with permutations

Let $a$ be vector in $R^{2m}$. And let $S_{2m}$ be group of all permutations on the set $\{1,\dots,2m\}$. I would like to calculate $$ \sup_{\pi\in S_{2m}}\sum_{d(\sigma, ...
3
votes
0answers
147 views

Maximum size of a Sperner family containing a set of a given size

Given a set $A$ of $n$ elements and an positive integer $k\le n$, what is the size of the largest Sperner family $\mathcal{F}$ of subsets of $A$ such that $\mathcal{F}$ contains a set $B\subseteq A$ ...
-1
votes
1answer
124 views

No of ways of allotting 4 dishes to n days [duplicate]

Possible Duplicate: In how many ways can we colour $n$ baskets with $r$ colours? There are n days and 4 types of dishes.Any 1 of 4 dishes is alloted to each day. And dishes of the ...
1
vote
3answers
74 views

Prove that $n!e-2$ $<$ $\displaystyle \sum_{k=1}^{n}(^{n}\textrm{P}_{k})$ $\leq$ $n!e-1$

Prove that $n!e-2$ $<$ $\sum_{k=1}^{n}(^{n}\textrm{P}_{k})$ $\leq$ $n!e-1$ where $^{n}\textrm{P}_k = n(n-1)\cdots(n-k+1)$ is the number of permutations of $k$ distinct objects from $n$ distinct ...
3
votes
1answer
132 views

What's wrong with this proof of Sperners theorem?

Sperners theorem is about antichains (subsets of powerset of n elements for which no pair of elements contains the other) for example if we choose from ...
1
vote
3answers
109 views

Simplify sum using a combinatorial identity

I want to show that $$ \sum_{i=0}^n {n\choose i} \left(x^{i+1}y^{n-i} + x^i y^{n-i+1}\right) = \sum_{i=0}^{n+1}{n+1 \choose i}x^i y^{n+1-i}. $$ I was thinking to split the sum on the LHR into 2 sums ...
0
votes
2answers
821 views

Lottery “Sum” forecasting

I was wondering if anyone can provide some mathematical insights to forecasting the "SUM" in this link as a time series. It is an oscillatory, range bound and poisson distribution. How can Monte Carlo ...
3
votes
2answers
691 views

Distributing a cake cut with four vertical slices among three people

A round cake was cut with a knife $4$ times vertically in such a way that it is cut to maximum number of pieces.Find the number of ways of distributing these cakes among three people such that ...
1
vote
2answers
141 views

Number of Sets problem

A class is attended by $n$ sophomores, $n$ juniors, and $n$ seniors. In how many ways can these students form $n$ sets of three people each if each set is to contain a sophomore, a junior, and a ...
2
votes
1answer
743 views

Statistic (Combination and Permutation)

I have this problem which I could not figure out if I should do it by using Combination or Permutation The Organizer of a television show must select 5 people to participate in the show. The ...
2
votes
2answers
647 views

Find the number of ways to write 17 as a sum of 1’s and 2’s if order is relevant.

Find the number of ways to write 17 as a sum of 1’s and 2’s if order is relevant.
1
vote
0answers
80 views

Is there research similar to Stringology, but with sequences of sets?

Is there research that applies to classical questions of stringology; maximal repetitions, pattern matching, longest repeated substring, .. but replaced the definition of string as a sequence of ...